package E_2024;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/*
一、题目描述
    在一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间间距固定为100米。

    每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

二、输入描述
    第一行为一个数N，表示路灯个数，1<=N<=100000。

    第二行为N个空格分隔的数，表示路径的照明半径，1<=照明半径<=100000*100。

三、输出描述
    第一个路灯和最后一个路灯之间，无法照明的区间的长度和。

四、解题思路
    题目要求计算第一个路灯和最后一个路灯之间无法照明的区间的长度和。

    例如：
    3
    20 70 30
    路灯1 覆盖0-20
    路灯2 覆盖30-170
    路灯3 覆盖170-230
    没被覆盖的区间只有20~30。

    所以输出10。
 */
public class E_100_38 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{20 ,70 ,30}));
        System.out.println(ans(new int[]{20 ,70 ,175 ,10}));
    }
    // 记录每一个路灯照亮的前后坐标
    // 按路灯能够照亮的最左侧坐标顺序排列
    // 判断两个路灯之间照明范围的覆盖情况
    //
    public static int ans(int[] arr){
        List<Integer[]> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int x = arr[i];
            int length = i * 100; 
            list.add(new Integer[]{length - x, length + x});
        }
        // 按路灯的最左侧照明坐标排序
        list.sort(Comparator.comparing(a->a[0]));
        int ans = 0;
        for (int i = 0; i < list.size() - 1; i++) {
            // 当前路灯的照明范围
            Integer[] is = list.get(i);
            // 下一个路灯的照明范围
            Integer[] as = list.get(i + 1);
            // 检查下一路灯的最远照明距离与当前路灯最远照明距离，若当前路灯最远照明距离大于下一路灯距离时，下一路灯最远照明距离需要修改为当前路灯最远照明距离
            if (is[1] >= as[0]) as[1] = is[1];
            ans += Math.max(0, as[0] - is[1]);
        }
        return ans;
    }
}
